package com.zhaopin.theswordreferstooffer;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yin.peide
 * @date 2021-06-16 11:29
 * 面试题25: 二叉树中和为某一值的路径
 *
 * 结果
 * [5, 4, 11, 2]
 * [5, 8, 4, 5]
 */
public class Offer25 {

    public static void main(String[] args) {
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode1 = new TreeNode(1);

        TreeNode treeNode11 = new TreeNode(11);
        TreeNode treeNode13 = new TreeNode(13);
        TreeNode treeNode4 = new TreeNode(4);

        TreeNode treeNode4N = new TreeNode(4);
        TreeNode treeNode8 = new TreeNode(8);

        TreeNode treeNode5R = new TreeNode(5);

        treeNode11.init(treeNode7,treeNode2);
        treeNode4.init(treeNode5,treeNode1);

        treeNode4N.setLeft(treeNode11);
        treeNode8.init(treeNode13,treeNode4);

        treeNode5R.init(treeNode4N,treeNode8);

        Solution solution = new Solution();
        List<List<Integer>> lists = solution.pathSum(treeNode5R, 22);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }

        List<List<Integer>> lists1 = solution.pathSumDeep(treeNode5R, 22);
        for (List<Integer> list : lists1) {
            System.out.println(list);
        }

        System.out.println("--------------------------");
        List<List<Integer>> lists2 = solution.onlyDeep(treeNode5R);
        for (List<Integer> list : lists2) {
            System.out.println(list);
        }
    }




}


class Solution {

    public List<List<Integer>> pathSumDeep(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, sum, new ArrayList<>(), result);
        return result;
    }

    public void dfs(TreeNode root, int sum, List<Integer> list, List<List<Integer>> result) {
        //如果节点为空直接返回
        if (root == null){
            return;
        }
        //因为list是引用传递，为了防止递归的时候分支污染，我们要在每个路径
        //中都要新建一个subList
        List<Integer> subList = new ArrayList<>(list);
        //把当前节点值加入到subList中
        subList.add(new Integer(root.getValue()));
        //如果到达叶子节点，就不能往下走了，直接return
        if (root.getLeft() == null && root.getRight() == null) {
            //如果到达叶子节点，并且sum等于叶子节点的值，说明我们找到了一组，
            //要把它放到result中
            if (sum == root.getValue()){
                result.add(subList);
            }

            //到叶子节点之后直接返回，因为在往下就走不动了
            return;
        }
        //如果没到达叶子节点，就继续从他的左右两个子节点往下找，注意到
        //下一步的时候，sum值要减去当前节点的值
        dfs(root.getLeft(), sum - root.getValue(), subList, result);
        dfs(root.getRight(), sum - root.getValue(), subList, result);
    }


    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, sum, 0, new ArrayList<>(), result);
        return result;
    }

    public void dfs(TreeNode root, int sum, int toal, List<Integer> list, List<List<Integer>> result) {
        //如果节点为空直接返回
        if (root == null) {
            return;
        }
        //把当前节点值加入到list中
        list.add(new Integer(root.getValue()));
        //没往下走一步就要计算走过的路径和
        toal += root.getValue();
        //如果到达叶子节点，就不能往下走了，直接return
        if (root.getLeft() == null && root.getRight() == null) {
            //如果到达叶子节点，并且sum等于toal，说明我们找到了一组，
            //要把它放到result中
            if (sum == toal) {
                result.add(new ArrayList(list));
            }

            //注意别忘了把最后加入的结点值给移除掉，因为下一步直接return了，
            //不会再走最后一行的remove了，所以这里在rerurn之前提前把最后
            //一个结点的值给remove掉。
            list.remove(list.size() - 1);
            //到叶子节点之后直接返回，因为在往下就走不动了
            return;
        }
        //如果没到达叶子节点，就继续从他的左右两个子节点往下找
        dfs(root.getLeft(), sum, toal, list, result);
        dfs(root.getRight(), sum, toal, list, result);
        //我们要理解递归的本质，当递归往下传递的时候他最后还是会往回走，
        //我们把这个值使用完之后还要把它给移除，这就是回溯
        list.remove(list.size() - 1);
    }


    /**
     * 只遍历所有路径 较牛方法
     * @param root
     * @return
     */
    public List<List<Integer>> onlyDeep(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, new ArrayList<>(), result);
        return result;
    }

    public void dfs(TreeNode root,  List<Integer> list, List<List<Integer>> result) {
        //如果节点为空直接返回
        if (root == null){
            return;
        }
        //因为list是引用传递，为了防止递归的时候分支污染，我们要在每个路径
        //中都要新建一个subList
        List<Integer> subList = new ArrayList<>(list);
        //把当前节点值加入到subList中
        subList.add(new Integer(root.getValue()));
        //如果到达叶子节点，就不能往下走了，直接return
        if (root.getLeft() == null && root.getRight() == null) {
            //如果到达叶子节点，并且sum等于叶子节点的值，说明我们找到了一组，
            //要把它放到result中
            result.add(subList);

            //到叶子节点之后直接返回，因为在往下就走不动了
            return;
        }
        //如果没到达叶子节点，就继续从他的左右两个子节点往下找，注意到
        //下一步的时候，sum值要减去当前节点的值
        dfs(root.getLeft(), subList, result);
        dfs(root.getRight(), subList, result);
    }

}
